<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>4650：[Noi2016]优秀的拆分</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Noi2016]优秀的拆分</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Noi2016]优秀的拆分</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Noi2016]优秀的拆分                </h1>
                <p>时间限制：30s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：512MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>
<div>如果一个字符串可以被拆分为 AABBAABB 的形式，其中 AA 和 BB 是任意非空字符串，则我们称该字符串的这种拆</div>
<div>分是优秀的。例如，对于字符串 aabaabaa，如果令 A=aabA=aab，B=aB=a，我们就找到了这个字符串拆分成 AABBA</div>
<div>ABB 的一种方式。一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=aA=a，B=baa</div>
<div>B=baa，也可以用 AABBAABB 表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。现在给出一个长度为</div>
<div>&nbsp;nn 的字符串 SS，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串</div>
<div>中连续的一段。以下事项需要注意：出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被</div>
<div>记入答案。在一个拆分中，允许出现 A=BA=B。例如 cccc 存在拆分 A=B=cA=B=c。字符串本身也是它的一个子串。</div>
<div></div>
</div>
<div></div></p><hr/><h3>输入格式</h3><p><div>每个输入文件包含多组数据。输入文件的第一行只有一个整数 TT，表示数据的组数。保证 1&le;T&le;101&le;T&le;10。接</div>
<div>下来 TT 行，每行包含一个仅由英文小写字母构成的字符串 SS，意义如题所述。</div></p><hr/><h3>输出格式</h3><p><p>输出 TT 行，每行包含一个整数，表示字符串 SS 所有子串的所有拆分中，总共有多少个是优秀的拆分。</p></p><hr/><h3>样例输入</h3><pre>4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba</pre><hr/><h3>样例输出</h3><pre>3
5
4
7
我们用 S[i,j]S[i,j] 表示字符串 SS 第 ii 个字符到第 jj 个字符的子串（从 11 开始计数）。第一组数据中，
共有 33 个子串存在优秀的拆分：S[1,4]=aabbS[1,4]=aabb，优秀的拆分为 A=aA=a，B=bB=b；S[3,6]=bbbbS[3,6]
=bbbb，优秀的拆分为 A=bA=b，B=bB=b；S[1,6]=aabbbbS[1,6]=aabbbb，优秀的拆分为 A=aA=a，B=bbB=bb。而剩
下的子串不存在优秀的拆分，所以第一组数据的答案是 33。第二组数据中，有两类，总共 44 个子串存在优秀的
拆分：对于子串 S[1,4]=S[2,5]=S[3,6]=ccccS[1,4]=S[2,5]=S[3,6]=cccc，它们优秀的拆分相同，均为 A=cA=c，
B=cB=c，但由于这些子串位置不同，因此要计算 33 次；对于子串 S[1,6]=ccccccS[1,6]=cccccc，它优秀的拆分
有 22 种：A=cA=c，B=ccB=cc 和 A=ccA=cc，B=cB=c，它们是相同子串的不同拆分，也都要计入答案。所以第二组
数据的答案是 3+2=53+2=5。第三组数据中，S[1,8]S[1,8] 和 S[4,11]S[4,11] 各有 22 种优秀的拆分，其中 S[1
,8]S[1,8] 是问题描述中的例子，所以答案是 2+2=42+2=4。第四组数据中，S[1,4]S[1,4]，S[6,11]S[6,11]，S[7
,12]S[7,12]，S[2,11]S[2,11]，S[1,8]S[1,8] 各有 11 种优秀的拆分，S[3,14]S[3,14] 有 22 种优秀的拆分，
所以答案是 5+2=75+2=7。</pre><hr/><h3>提示</h3><p>没有写明提示</p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=4650" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=4650" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>